Всем известна табличка сложности операций над словарями в питоне:
Операция | Средняя сложность | Худший вариант |
---|---|---|
get | O(1) | O(n) |
set | O(1) | O(n) |
delete | O(1) | O(n) |
copy | O(n) | O(n) |
iterate | O(n) | O(n) |
Оказалось, что n
в этой таблице — вовсе не текущий размер словаря, а тот размер, до которого словарь когда-либо
дорастал в своей жизни.
Вот у вас был словарик в 20 элементов, n = 20
. Вы в него прочитали что-то большое из базы данных, например; словарик
потолстел до 2000 элементов. n = 2000
. Так вот если сейчас провести удаление 1880 элементов из словаря, его n
всё
равно будет равно двум тысячам, и итерирование по нему будет происходить очень медленно.
Что делать? В таких случаях стоит создавать новый словарь вместо удаления элементов из старого. Так победим! (что-то невнятно пробурчал про иммутабельность и умолк)